package 排序算法.桶排序;



import 动态链表.LinkedList;

import java.util.Arrays;
import java.util.Comparator;

public class BucketSort {
    public static void main(String[] args) {
        int[] arr= {8,9,58,5,6,3,5,87,0,5,5};
        bucketSort(arr);

        System.out.println(Arrays.toString(arr));
    }

    private static void bucketSort(int[] arr) {
        int min = findMin(arr);
        int max = findMax(arr);
        int bucketNum = (max - min) / 10 + 1;
        LinkedList<Integer>[] list = new LinkedList[bucketNum];
        for (int i = 0; i < list.length; i++) {
            list[i] = new LinkedList<>();
        }

        for (int i = 0; i < arr.length; i++) {
            list[(arr[i] - min) / 10].add(arr[i]);
        }

        for (int i = 0; i < list.length; i++) {
            list[i].sort(new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return o1 - o2;
                }
            });
        }

        int index = 0;
        for (int i = 0; i < list.length; i++) {
            while (!list[i].isEmpty()){
                arr[index++] = list[i].removeFirst();
            }
        }

    }

    private static int findMin(int[] arr) {
        int min = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < min){
                min = arr[i];
            }
        }
        return min;
    }

    private static int findMax(int[] arr) {
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max){
                max = arr[i];
            }
        }
        return max;
    }
}
